package algorithms.search;

import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Queue;

/**
 * 平衡搜索树
 * @author glogo
 *
 */
public class BST<Key extends Comparable, Value> {

	private Node root;
	
	private class Node{
		private Key key;
		private Value val;
		private Node left, right;	
		private int N;	
		
		public Node(Key key, Value val, int N) {
			this.key = key;	this.val = val; this.N = N;
		}
	}
	
	public boolean isEmpty(){
		return size() == 0;
	}
	
	// does there exist a key-value pair with given key?
    public boolean contains(Key key) {
        return get(key) != null;
    }
	
	public int size(){
		return size(root);
	}
	
	private int size(Node x){
		if(x == null)	return 0;
		else			return x.N;
	}
	
	public Value get(Key key){
		return get(root, key);
	}
	
	
	public void put(Key key, Value val){
		root = put(root, key, val);
	}
	
	public Key min(){
		return min(root).key;
	}
	
	private Node min(Node x){
		if(x.left == null)	return x;
		return min(x.left);
	}
	
	public Key max(){
		return max(root).key;
	}
	
	private Node max(Node x){
		if(x.right == null)		return x;
		return max(x.right);
	}
	
	public Key floor(Key key){
		Node x = floor(root, key);
		if(x == null)	return null;
		return x.key;
	}
	
	private Node floor(Node x, Key key){
		if(x == null)	return null;
		int cmp = key.compareTo(x.key);
		if(cmp == 0)	return x;
		if(cmp  < 0)	return floor(x.left, key);
		Node t = floor(x.right, key);
		if(t != null)	return t;
		else			return x;
	}
	
	public Key ceiling(Key key){
		Node x = ceiling(root, key);
		if(x == null)	return null;
		else			return x.key;
	}
	
	private Node ceiling(Node x, Key key){
		if(x == null)	return null;
		int cmp = key.compareTo(x.key);
		if(cmp == 0)		return x;
		if(cmp  > 0)		return floor(x.right, key);
		Node t = floor(x.left, key);
		if(t != null)		return t;
		else 				return x;
	}
	
	public Key select(int k){
		return select(root, k).key;
	}
	
	private Node select(Node x, int k){
		if(x == null)	return null;
		int t = size(x.left);
		if(t > k)		return select(x.left, k);
		else if(t < k)		return select(x.right, k);
		else					 return x;
	}
	
	private Value get(Node x, Key key){
		if(x == null)	return null;
		int cmp = key.compareTo(x.key);
		if(cmp < 0)		return get(x.left, key);
		else if(cmp > 0)	return get(x.right, key);
		else 					return x.val;
	}
	
	/***********************************************************************
	    *  Insert key-value pair into BST
	    *  If key already exists, update with new value
	    ***********************************************************************/
	private Node put(Node x ,Key key, Value val){
		if(x == null)	return new Node(key, val, 1);
		int cmp = key.compareTo(x.key);
		if(cmp < 0)		x.left = put(x.left, key, val);
		else if(cmp > 0) x.right = put(x.right, key, val);
        else    x.val = val;
		x.N = size(x.left) + size(x.right) + 1;
		return x;
	}
	
	public int rank(Key key){
		return rank(root, key);
	}
	
	private int rank(Node x, Key key){
		if(x == null)		return 0;
		int cmp = key.compareTo(x.key);
		if(cmp < 0)		return rank(x.left, key);
		else if(cmp > 0)	return rank(x.right, key);
		else					return size(x.left);
	}
	
	/***********************************************************************
	    *  Delete
	    ***********************************************************************/
	public void deleteMin(){
		if(isEmpty())	throw new NoSuchElementException("Symbol table underflow!");
		root = deleteMin(root);		
//		assert check();
	}
	
	
	private Node deleteMin(Node x){
		if(x.left == null)		return x.right;
		x.left = deleteMin(x.left);
        x.N = size(x.left) + size(x.right) + 1;
        return x;
	}
	
	public void deleteMax() {
        if (isEmpty()) throw new NoSuchElementException("Symbol table underflow");
        root = deleteMax(root);
//        assert check();
    }

    private Node deleteMax(Node x) {
        if (x.right == null) return x.left;
        x.right = deleteMax(x.right);
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }
	
    public void delete(Key key){
    	root = delete(root, key);
    }
    
    
    private Node delete(Node x, Key key){
    	if(x == null)	return null;
    	int cmp = key.compareTo(x.key);
    	if(cmp < 0)		x.left = delete(x.left, key);
    	else if(cmp > 0)	x.right = delete(x.right, key);
    	else{		
    		if(x.right == null)		return x.left;
    		if(x.left  == null)		return x.right;
    		Node t = x;
    		x = min(t.right);
    		x.right = deleteMin(t.right);
    		x.left  = t.left;
    	}
    	x.N = size(x.left) + size(x.right) + 1;
    	return x;		
    }
	
    private void print(Node x){
    	if(x == null)	return ;
    	print(x.left);
    	System.out.println(x.key + "-" + x.val);
    	print(x.right);
    }

    public Iterable<Key> keys(){
    	return keys(min(), max());
    }
    
    public Iterable<Key> keys(Key lo, Key hi){
    	Queue<Key> queue = new LinkedList<Key>();
    	keys(root, queue, lo, hi);
    	return queue;
    }
    

	private void keys(Node x, Queue<Key> queue, Key lo, Key hi){
    	if(x == null)		return;
    	int cmplo = lo.compareTo(x.key);
    	int cmphi = hi.compareTo(x.key);
    	if(cmplo < 0)	keys(x.left, queue, lo, hi);
    	if(cmplo <=0 && cmphi >= 0)	queue.offer(x.key);
    	if(cmphi > 0)			keys(x.right, queue, lo, hi);
    }
    
   
    public Iterable<Key> keys2(){
    	return keys2(root);
    }
    
    private Iterable<Key> keys2(Node x){
    	Queue<Key> queue = new LinkedList<Key>();
    	Queue<Node> q2    = new LinkedList<Node>();
    	q2.offer(root);
    	while(!q2.isEmpty()){
    		Node tmpK = q2.poll();
    		q2.offer(tmpK.left);
    		q2.offer(tmpK.right);
    		queue.offer(tmpK.left.key);
    		queue.offer(tmpK.right.key);
    	}
    	return queue;
    }
    
 // height of this BST (one-node tree has height 0)
    public int height() { return height(root); }
    private int height(Node x) {
        if (x == null) return -1;
        return 1 + Math.max(height(x.left), height(x.right));
    }
    
    
    public boolean isBinaryTree(Node x){
    	if(x == null)	return true;
    	boolean m = (x.N ==( x.left.N + x.right.N + 1));
    	if(!m)
    		return m;
    	else{
    		m = isBinaryTree(x.left);
    		if(!m)	return m;
    		m = isBinaryTree(x.right);
    	}
    	return m;
    }
    
    public boolean isOrdered(Node x, Key min, Key max){
    	return false;
    }
    
    public static boolean isBST(){


    	return false;
    }

    @Override
    public String toString() {
        print(root);
        return "";
    }

    public static void main(String[] args) {
        BST<String, Integer> bst = new BST<String, Integer>();
        bst.put("A", 1);
        bst.put("B", 2);
        bst.put("C", 3);
        bst.put("C", 4);
        System.out.println(bst);
        System.out.println(bst.size());
	}
}



